package practice;

import javax.swing.text.AbstractDocument;
import java.util.*;


class ListNode {
    int val;
    ListNode next = null;public ListNode(int val) {
        this.val = val;
    }
}

public class Day23 {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode ret = new ListNode(0);
        ret.next = head;
        ListNode prev = ret;
        while (m != 0) {
            prev = prev.next;
            m--;
        }
        ListNode last = null;
        ListNode cur = null;
        int len = n-m+1;
        while (len != 0 && prev != null) {
            ListNode curNext = prev.next;
            head.next = prev;
            prev.next = cur;
            cur = prev;
            last = prev;
            prev = curNext;
            len--;
        }
        last.next = prev;
        return ret.next;
    }

    public static int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(j+nums[j] >= i) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        return dp[n-1];
    }

    //记忆化搜索
    int[][] memo;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int n = 0;
    int m = 0;
    private int dfs(int[][] matrix,int i,int j) {
        if(memo[i][j] != -1) {
            return memo[i][j];
        }
        int len = 1;
        for(int k = 0; k < 4; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]) {
                len = Math.max(len,dfs(matrix,x,y)+1);
            }
        }
        memo[i][j] = len;
        return len;
    }
    public int solve (int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        memo = new int[n][m];
        int ret = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                memo[i][j] = -1;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                ret = Math.max(ret,dfs(matrix,i,j));
            }
        }
        System.out.println(memo[1][1]);
        return 1;

    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return a[0] - b[0];
        });
        int n = intervals.length;
        List<int[]> list = new LinkedList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < n; i++) {
            int a = intervals[i][0];
            int b = intervals[i][1];
            if(a <= right) {
                //合并区间
                right = Math.max(right,b);
            }else {
                //不用合并区间，直接添加
                list.add(new int[]{left,right});
                left = a;
                right = b;
            }
        }
        list.add(new int[]{left,right});
        int k = 0;
        int[][] ret = new int[list.size()][2];
        while(!list.isEmpty()) {
            ret[k++] = ((LinkedList<int[]>) list).pollFirst();
        }
        return ret;
    }

    public int[] fun(int[] nums, int target) {
        Arrays.sort(nums);
        int[] ret = new int[2];
        int n = nums.length;
        int left = 0;
        int right = n-1;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum < target) {
                left++;
            }else if(sum > target) {
                right--;
            }else if(sum == target) {
                ret[0] = left;
                ret[1] = right;
                break;
            }
        }
        return ret;
    }
}
